/*
    Author: Christopher Diggins
    License: MIT Licence 1.0
    Website: http://www.cdiggins.com
*/

#ifndef CVML_SUBROUTINE_GEN_HPP
#define CVML_SUBROUTINE_GEN_HPP

void ReplaceSeqWithCall(Subroutine* sub, InstrSeq seq) {
    for (Instruction* i=seq.begin; i != seq.end; i = i->next) 
        i->SetNoop();
    seq.begin->SetOpCode(op_push_sub, sub);
	seq.begin->AddInstruction(op_apply);
}

Subroutine* CreateSubFromSeq(ByteCode* bc, InstrSeq seq) {
	Subroutine* sub = bc->NewSub();
    Instruction* cur = sub->first;
    for (Instruction* i=seq.begin; i != seq.end; i = i->next) {
        cur = cur->AddInstruction(*i);
    }
    cur->AddInstruction(op_ret);
    return sub;
}

int ComputeCost(std::vector<InstrSeq>& seqs) {    
    // TODO: 
	int width = seqs[0].GetWidth();
	int count = seqs.size();
    int cost = width + 1; // 1 is the size of op_ret
    int savings = width - 3; // 3 is the length of a "push_short" + apply. 
    cost -= count * savings;
    return cost;
}

void CopySeqs(std::vector<InstrSeq>& src, std::vector<InstrSeq>& dest) {
    dest.clear();
    for (size_t i=0; i < src.size(); ++i) {
        for (size_t j=0; j < src.size(); ++j) {
            if (i != j) {
                if (src[i].MatchesWithoutOverlap(src[j])) {
                    dest.push_back(src[i]);
                    break;
                }
            }
        }
    }
}

bool IncreaseLength(std::vector<InstrSeq>& src) {
    bool b = false;
    for (size_t i=0; i < src.size(); ++i) {
        if (src[i].end != NULL && src[i].end->opcode != op_ret) {
            src[i].end = src[i].end->next;
            b = true;
        }
    }
    return b;
}

// TODO: document this algorithm it isn't clear
void GenerateSubsFromPrefixNode(ByteCode* bc, PrefixTree::Node* node) {
    if (node->seqs.size() < 2)  {
        return;    
    }

    int cost = 1000; // Some arbitrarily large number
    std::vector<InstrSeq> seqs; 
    CopySeqs(node->seqs, seqs);
    
	// If there aren't at least two common sequences, we can't make it into a subroutine.
	if (seqs.size() < 2) {
        return;
    }

    std::vector<InstrSeq> best; 
    CopySeqs(node->seqs, seqs);
    while (seqs.size() >= 2) {
        int tmp = ComputeCost(seqs);
        if (tmp < cost) { 
            cost = tmp;
            best = seqs;
        }
        std::vector<InstrSeq> prev(seqs);
        if (!IncreaseLength(prev))
            break;
        CopySeqs(prev, seqs);
    }

    // We now have a "best" list of sequences and a cost
	// A positive cost, means there is no space saving benefit.
    if (cost > 0) 
        return; 

    Assert(best.size() > 1);

    // Now create the subroutines
    Subroutine* sub = CreateSubFromSeq(bc, best[0]);
    for (size_t i=0; i < best.size(); ++i)
        ReplaceSeqWithCall(sub, best[i]);
}

PrefixTree* CreatePrefixTree(ByteCode* bc, int length) {
	bc->StripNoops();    
	PrefixTree* r = new PrefixTree(length);
    for (int i=0; i < bc->GetNumSubs(); ++i) 
	{
		Subroutine* sub = bc->GetSub(i);
        for (Instruction* cur = sub->first; cur != NULL; cur = cur->next)
        {
			InstrSeq seq(cur, length);
			if (seq.Len() != length)
				break;
            r->AddSeq(seq);
        }
    }
	return r;
}

void GenerateSubs(ByteCode* bc) {
	PrefixTree* prefixes = CreatePrefixTree(bc, 2);
    std::vector<PrefixTree::Node*> leaves;
    prefixes->GetLeaves(leaves);
    for (size_t i=0; i < leaves.size(); ++i) {
        GenerateSubsFromPrefixNode(bc, leaves[i]);
    }
    std::vector<InstrSeq> vec;
    GenerateSubsFromPrefixNode(bc, prefixes->root);
    bc->StripNoops();
	delete prefixes;
}

#endif
